package puzzle.projecteuler.p300;

public class Problem265C {

	/**
	 * 只要考虑所有以"000001"开头，以"1"结尾的所有32位整数就可以。
	 * 中间部分对应的数值介于0~2^25-1，并且恰包含11个0,14个1。
	 * 
	 * answer: 209110240768
	 * time: 64765 ms
	 *  
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		
		long s = s(5);
		System.out.println(s);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}

	private static long s(int N) {
		
		int N2 = 1<<N;
		int MAX = (1<<(N2-N-2));
		char[] cs = new char[N2];
		for (int i = 0; i < N; i ++) cs[i] = '0';
		cs[N] = '1';
		cs[N2-1] = '1';
		
		long s = 0;
		int count = 0;
		for (int i = 0; i < MAX; i ++) {
		
			char[] ts = Integer.toBinaryString(i).toCharArray();
			int c1 = 0;
			for (int j = 0; j < ts.length; j ++) {
				if (ts[j] == '1') c1 ++;
			}
			if (c1 != (N2>>1)-2) {
				continue;
			} else {
				for (int j = N+1; j < N2-1; j ++) cs[j] = '0';
				for (int j = N2-1-ts.length; j <= N2-2; j ++) cs[j] = ts[ts.length+j-N2+1];
				if (check(N, cs)) {
					String t = String.valueOf(cs);
					long a = Long.valueOf(t, 2);
					s += a;
					count ++;
					System.out.println(String.format("%4d: %s = %d", count+1, t, a));
				}
			}
		}
		return s;
	}

	private static boolean check(int N, char[] cs) {

		int N2 = 1<<N;
		int[] ns = new int[N2];
		for (int i = 0; i < N2; i ++) {
			char[] ts = new char[N];
			for (int j = 0; j < N; j ++) {
				ts[j] = cs[(i+j)%N2];
			};
			ns[i] = Integer.valueOf(String.valueOf(ts), 2);
		}
		
		for (int i = 0; i < N2; i ++) {
			for (int j = i+1; j < N2; j ++) {
				if (ns[i] == ns[j]) return false; 
			}
		}
		return true;
	}

}
